In the field of public key cryptography, each user holds a pair of keys for a given use, the pair of keys comprising a secret key and an associated public key. In the case of a pair of keys dedicated to confidentiality, for example, the public key is used to encrypt the data and the secret key is used to decrypt it, i.e. to recover the data in clear. In contrast, in the case of a pair of keys dedicated to authentication, the secret key is used to calculate authentication values and the public key is used to verify the authentication values. Other uses are also possible, such as digital signatures and exchanging keys.
Public key cryptography is very useful in that, unlike secret key cryptography, it does not require the parties to share the same secret to set up secure communication. However, this advantage in terms of security goes hand in hand with a disadvantage in terms of performance, since public key cryptography methods (also known as public key schemes) are often a hundred or a thousand times slower than secret key cryptography methods (also known as secret key schemes). Finding fast execution public key cryptography methods that can be used in the environments with limited resources referred to above, such as microprocessor cards, is a very considerable challenge.
Most existing public key schemes rely on the difficulty of mathematical problems from the field of arithmetic or number theory. Thus the security of the RSA (Rivest, Shamir and Adleman) encryption and electronic signature scheme relies on the difficulty of the problem of factoring integers: given a large integer (i.e. one of more than 1000 bits) equal to the product of two or more prime factors of comparable size, there is no effective method of recovering the prime factors.
Other public key schemes, such as the electronic signature scheme described in French Patent No. 2 716 058, rely for their security on the difficulty of the discrete logarithm problem. All these schemes have the common feature of using basic operations in the form of operations on integers, such as modular multiplication: ab (modulo n), modular division: a/b (modulo n), or modular exponentiation: ab (modulo n), where a and b are integers.
The fact that most existing public key schemes rely on arithmetic has at least two drawbacks.
The first drawback is that, if the integers concerned have a length of a few hundred bits, the existence of efficient algorithms for solving the factoring problem and the discrete logarithm problem implies using very long integers (in particular very long keys), meaning 1000 bits or more at present. This leads to storage problems and especially to very long calculation times. Moreover, as the efficiency of these algorithms is increasing fairly rapidly as time passes, key lengths must be increased accordingly.
The second disadvantage is that it is risky to base the security of most secure applications on the difficulty of only two mathematical problems. This is especially true in that the two problems are similar, and it is entirely likely that the discovery of an efficient algorithm for solving one of them will be accompanied by the discovery of an efficient algorithm for solving the other.
This is why, for around the past fifteen years, much effort has been devoted to constructing public key cryptographic schemes that rely on problems other than those mentioned above and/or on mathematical objects other than integers. In particular, it has been proposed to replace operations on integers with operations on the points of so-called elliptical curves. The motivation for this is that the discrete logarithm problem seems even more difficult to solve in the case of elliptical curves, which reduce the lengths of keys without compromising the security of the schemes concerned.
However, using elliptical curves is only a partial solution to the two problems referred to hereinabove. This is because, even if elliptical curves are mathematical objects differing from and more complex than sets of integers, they remain relatively close thereto, in the sense that the theory that describes them is closely related to number theory. One tangible effect of this similarity is that the calculations to be applied to elliptical curves reduce to a succession of operations on integers similar to those defined above, even if the integers are smaller. A consequence of this is that calculation times remain too long.
For cryptographic purposes, it therefore remains necessary to use mathematical objects that are very different from those of number theory and the like, firstly to provide back-up solutions in the event of the discovery of efficient algorithms for solving the problems on which the above theories rely and, secondly, to provide solutions that are extremely efficient in terms of performance and in particular in terms of calculation time.
Attempts have been made in this direction. One of them (see K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang, and C. Park, New Public-Key Cryptosystem Using Braid Groups, Advances in Cryptology, LNCS 1880, pp. 166-183, Springer Verlag, August 2000) consists in using mathematical objects known as braid groups.
In the mathematical sense, a braid is a conceptualization and a generalization of the braid concept in the geometrical sense and in the ordinary use of the term. For more details on the theory of braids see the article by P. Dehornoy, L'art de tresser [The art of braiding], published in Pour la Science, pp. 68-75, of a special issue in 1997 entitled La science des noeuds [The science of knots].
The set of braids with n strands constitutes a group G, which has an internal composition law called a product which associates two braids X and Y with a braid XY resulting from the operation of attaching the braid Y under the braid X. As a general rule, the product of braids is not commutative. Moreover, with any braid with n strands there may be uniquely associated a permutation of the set {1, 2, . . . , n}. A braid whose permutation is the identity permutation (which sends any integer from 1 to n to itself) is said to be pure.
The group G of braids with n strands has a neutral element E, represented by n unbraided strands, such that, for any braid X, the products EX and XE are both equal to X. Moreover, any braid X has an inverse X−1 such that the products XX−1 and X−1X are both equal to E.
The braids with n strands of the group G may be coded in various ways known as representations. To code a braid in a given representation, it is associated with one or more representatives. If X is a braid, x is a representative of X in the underlying representation. In the usual representations, such as those used by the present invention, if a braid X and a braid Y have respective representatives x and y, then there exists a simple operation on x and y whose result xy is a representative of the braid XY, and likewise there exists a simple operation on x whose result x−1 is a representative of the braid X−1.
The most widespread, so-called standard representation is based on the fact that any braid may be broken down into a product of (n−1) individual braids, each of which is denoted by a letter of an alphabet, and their inverses. Lowercase letters are used for the representatives of the individual braids. For example, in the case of braids with four strands, the three individual braids are denoted A, B and C, with the result that any braid X of the group may be expressed in a non-unique manner as a function of the braids A, B, C and their inverses A−1, B−1, C−1. For example, the braids ABA and BAB are equal. Now aba and bab are equivalent braid representatives, i.e. they represent the same braid. Similarly, the braid B is equal to the braid BBB−1, with the result that the representatives b and bbb−1 are equivalent.
Other representations of the group G, referred to as alternative representations, may be employed. Thus a braid with n strands may be coded as a product of simple or canonic braids represented by permutations of {1, 2, . . . , n} and their inverses. There is also a representation of G known as the Birman-Ko-Lee representation, in which coding again uses permutations or certain tables of n numbers or from 1 to n, and another representation, known as the Dynnikov representation, in which coding is effected by means of integers. Once again a braid may have a plurality of representatives and representatives of the same braid are said to be equivalent.
In the standard representation, in which a braid is coded by words, the notation “˜” means “equivalent to”. The notation “u˜v”, in which u is a representative of the braid U and v is a representative of the braid V, means that the braids U and V are equal. The following relations of equivalence provide an exact way to determine if two words represent the same braid:                aa−1˜a−1a˜e,        ac˜ca if a and c are non-consecutive letters,        aba˜bab if a and b are consecutive letters.        The above-mentioned public key cryptography method using braids is dedicated exclusively to the confidentiality of data that is encrypted before transmission and then decrypted by the recipient.        